package fun.ticsmyc.question;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 矩阵对角线遍历和旋转 {

    //54. 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();

        int lx=0,ly=0;
        int rx = matrix.length-1,ry=matrix[0].length-1;
        while(lx<rx && ly<ry){
            route(matrix,lx,ly,rx,ry,res);
            lx++; ly++;
            rx--;ry--;
        }
        if(ly < ry && lx==rx ){
            for (int i = ly; i <=ry; i++) {
                res.add(matrix[lx][i]);
            }
        }else if(lx < rx && ly==ry){
            for (int i = lx; i <= rx; i++) {
                res.add(matrix[i][ly]);
            }
        }else if(ly==ry && lx == rx){
            res.add(matrix[lx][ly]);
        }
        return res;
    }

    private void route(int[][] matrix, int lx,int ly,int rx, int ry, List<Integer> res) {
        //lx,ly  ->  lx,ry   -> rx,ry  ->  rx,ly -> lxly
        for (int i = ly; i <ry ; i++) {
            res.add(matrix[lx][i]);
        }
        for (int i = lx; i < rx;  i++) {
            res.add(matrix[i][ry]);
        }
        for (int i = ry; i > ly; i--) {
            res.add(matrix[rx][i]);
        }
        for (int i = rx; i >lx ; i--) {
            res.add(matrix[i][ly]);
        }
    }


    //对角线遍历 498. 对角线遍历
    public int[] findDiagonalOrder(int[][] mat) {
        int[] res = new int[mat.length* mat[0].length];
        int index =0;

        boolean up=true;
        for (int i = 0; i < mat[0].length+mat.length-1; i++) {
            int uy = Math.min(mat[0].length-1,i);
            int ux = i-uy;
            int dx = Math.min(mat.length-1,i);
            int dy = i-dx;
            Deque<Integer> curRes = line(mat,ux,uy,dx,dy,up);
            for (int cur : curRes) {
                res[index++] = cur;
            }
            up = !up;
        }
        return res;
    }
    private Deque<Integer> line(int[][] mat, int ux, int uy, int dx, int dy, boolean up) {
        Deque<Integer> res = new LinkedList<>();
        while(dx >=ux && dy<=uy){
            int cur = mat[dx][dy];
            dx--;
            dy++;
            if(up){
                res.addLast(cur);
            }else{
                res.addFirst(cur);
            }
        }
        return res;
    }
}
